The document US2004/0067041 describes a recording medium having a data structure for managing reproduction of graphic data and recording and reproducing methods and apparatuses. The recording medium includes a graphic information area having at least one graphic image information segment and at least one palette information segment recorded therein. Each palette information segment provides color information. Each graphic image information segment provides reproduction information for reproducing one or more graphic images. Multiple color palettes are proposed, each palette corresponding to a different color depth of the main video that is between 8 bits and 24 bits.